package unionFindStudy;

import java.util.HashSet;
import java.util.Set;

public class UnionFindStudy01 {

    /**
     * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
     *
     *  
     *
     * 进阶：你可以设计并实现时间复杂度为 O(n) 的解决方案吗？
     *
     * 总结：动态规划关心的是前一个的状态，但是该题的边界条件确定很难，所以无法使用动态规划。
     * 学会使用hash的能够快速查找的特性
     * @param args
     */
    public static void main(String[] args) {

    }

    public static int longestConsecutive(int[] nums){
        if (nums == null || nums.length == 0){
            return 0;
        }
        //存放序列
        Set<Integer> nums_set = new HashSet<>();
        for (int num : nums) {
            nums_set.add(num);
        }
        //记录最长连续序列的长度
        int longestLen = 0;
        for (Integer num : nums_set) {
            //至关重要，减小时间复杂度
            if (nums_set.contains(num - 1))
                continue;
            int temp = num + 1;
            int count = 1;
            while (nums_set.contains(temp)){
                temp++;
                count++;
            }
            longestLen = Math.max(count, longestLen);
        }
        return longestLen;
    }
}
